We give a systematic technical exposition of the foundations of the theory of computably compact metric spaces. We discover several new characterizations of computable compactness and apply these characterizations to prove new results in computable analysis and effective topology. We also apply the technique of computable compactness to give new and less combinatorially involved proofs of known results from the literature. Some of these results do not have computable compactness or compact spaces in their statements, and thus these applications are (...) not necessarily direct or expected. (shrink)

Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-Löf random, and provide a new (...) characterization of Schnorr random real numbers in terms of prefix-free machines. We prove that unlike Martin-Löf random c.e. reals, not all Schnorr random c.e. reals are Turing complete, though all are in high Turing degrees. We use the machine characterization to define a notion of "Schnorr reducibility" which allows us to calibrate the Schnorr complexity of reals. We define the class of "Schnorr trivial" reals, which are ones whose initial segment complexity is identical with the computable reals, and demonstrate that this class has non-computable members. (shrink)

We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study the fine behaviour of K (...) for random α. Following work of Downey, Hirschfeldt and LaForte, we say that αK β iff there is a constant such that for all n, . We call the equivalence classes under this measure of relative randomness K-degrees. We give proofs that there is a random real α so that lim supn K−K=∞ where Ω is Chaitin's random real. One is based upon work of Solovay, and the other exploits a new idea. Further, based on this new idea, we prove there are uncountably many K-degrees of random reals by proving that μ=0. As a corollary to the proof we can prove there is no largest K-degree. Finally we prove that if n ≠ m then the initial segment complexities of the natural n- and m-random sets and Ω︀) are different. The techniques introduced in this paper have already found a number of other applications. (shrink)

We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. There is a (...) c.e. set A of density 1 such that every subset of A of density 1 is of high degree. We also study the extent to which c.e. sets A can be approximated by their computable subsets B in the sense that A\B has small density. There is a very close connection between the computational complexity of a set and the arithmetical complexity of its density and we characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study the notion of "computable at density r" where r is a real in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity, hyperimmunity, and cohesiveness. (shrink)

Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.

We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.

Jockusch showed that 2-generic degrees are downward dense below a 2-generic degree. That is, if a is 2-generic, and $0 < {\bf{b}} < {\bf{a}}$, then there is a 2-generic g with $0 < {\bf{g}} < {\bf{b}}.$ In the case of 1-generic degrees Kumabe, and independently Chong and Downey, constructed a minimal degree computable from a 1-generic degree. We explore the tightness of these results.We solve a question of Barmpalias and Lewis-Pye by constructing a minimal degree computable from a weakly (...) 2-generic one. While there have been full approximation constructions of ${\rm{\Delta }}_3^0$ minimal degrees before, our proof is rather novel since it is a computable full approximation construction where both the generic and the minimal degrees are ${\rm{\Delta }}_3^0 - {\rm{\Delta }}_2^0$. (shrink)

The Dushnik–Miller Theorem states that every infinite countable linear ordering has a nontrivial self-embedding. We examine computability-theoretical aspects of this classical theorem.

We study the complexity of (finitely-valued and transfinitely-valued) Euclidean functions for computable Euclidean domains. We examine both the complexity of the minimal Euclidean function and any Euclidean function. Additionally, we draw some conclusions about the proof-theoretical strength of minimal Euclidean functions in terms of reverse mathematics.

We solve a problem posed by Goncharov and Knight 639–681, 757]). More specifically, we produce an effective Friedberg enumeration of computable equivalence structures, up to isomorphism. We also prove that there exists an effective Friedberg enumeration of all isomorphism types of infinite computable equivalence structures.

We describe new results in parametrized complexity theory. In particular, we prove a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. We also study the parametrized complexity of analogues of PSPACE via certain natural problems concerning k-move games. Finally, we examine several aspects of the structural complexity of W [P] and related classes. For instance, we show that W[P] can be characterized in (...) terms of the DTIME ) and NP. (shrink)

Cenzer, D., R. Downey, C. Jockusch and R.A. Shore, Countable thin Π01 classes, Annals of Pure and Applied Logic 59 79–139. A Π01 class P {0, 1}ω is thin if every Π01 subclass of P is the intersection of P with some clopen set. Countable thin Π01 classes are constructed having arbitrary recursive Cantor- Bendixson rank. A thin Π01 class P is constructed with a unique nonisolated point A and furthermore A is of degree 0’. It is shown that (...) no set of degree ≥0” can be a member of any thin Π01 class. An r.e. degree d is constructed such that no set of degree d can be a member of any thin Π01 class. It is also shown that between any two distinct comparable r.e. degrees, there is a degree that contains a set which is of rank one in some thin Π01 class. It is shown that no maximal set can have rank one in any Π01 class, while there exist maximal sets of rank 2. The connection between Π01 classes, propositional theories and recursive Boolean algebras is explored, producing several corollaries to the results on Π01 classes. For example, call a recursive Boolean algebra thin if it has no proper nonprincipal recursive ideals. Then no thin recursive Boolean algebra can have a maximal ideal of degree ≥0”. (shrink)

We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE presentations and we show that the groups ${\mathbb {Z}, Z(p^{\infty})}$ , and the additive group of the rationals have LOGSPACE presentations over a standard universe such as the tally representation and the binary representation of the natural numbers. We also study the effective categoricity of such groups. For (...) example, we give conditions are given under which two isomorphic LOGSPACE structures will have a linear space isomorphism. (shrink)

In [Countable thin [Formula: see text] classes, Ann. Pure Appl. Logic 59 79–139], Cenzer, Downey, Jockusch and Shore proved the density of degrees containing members of countable thin [Formula: see text] classes. In the same paper, Cenzer et al. also proved the existence of degrees containing no members of thin [Formula: see text] classes. We will prove in this paper that the c.e. degrees containing no members of thin [Formula: see text] classes are dense in the c.e. degrees. We (...) will also prove that the c.e. degrees containing members of thin [Formula: see text] classes are dense in the c.e. degrees, improving the result of Cenzer et al. mentioned above. Thus, we obtain a new natural subclass of c.e. degrees which are both dense and co-dense in the c.e. degrees, while the other such class is the class of branching c.e. degrees 113–130] for nonbranching degrees and [T. A. Slaman, The density of infima in the recursively enumerable degrees, Ann. Pure Appl. Logic 52 155–179] for branching degrees). (shrink)

We solve a longstanding question of Rosenstein, and make progress toward solving a longstanding open problem in the area of computable linear orderings by showing that every computable ƞ-like linear ordering without an infinite strongly ƞ-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

This work contributes to the program of studying effective versions of “almost-everywhere” theorems in analysis and ergodic theory via algorithmic randomness. Consider the setting of Cantor space {0,1}N with the uniform measure and the usual shift. We determine the level of randomness needed for a point so that multiple recurrence in the sense of Furstenberg into effectively closed sets P of positive measure holds for iterations starting at the point. This means that for each k∈N there is an n such (...) that n,2n,…,kn shifts of the point all end up in P. We consider multiple recurrence into closed sets that possess various degrees of effectiveness: clopen, Π10 with computable measure, and Π10. The notions of Kurtz, Schnorr, and Martin-Löf randomness, respectively, turn out to be sufficient. We obtain similar results for multiple recurrence with respect to the k commuting shift operators on {0,1}Nk. (shrink)

Answering a question of Per Lindström, we show that there is no “plus-capping” degree, i.e. that for any incomplete r.e. degreew, there is an incomplete r.e. degreea>w such that there is no r.e. degreev>w witha∩v=w.

A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...) \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $x$\end{document} can be derived in a grammar \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $G$\end{document} in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps, or whether a permutation has a factorization of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} over a given set of generators. We show hardness and completeness for these problems for various levels of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W$\end{document} hierarchy. In particular, we show that Short TM Computation is complete for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W[1]$\end{document}. This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes. (shrink)

Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it (...) is shown that the class FPT of tractable parameterized problems has interesting and natural internal structure. (shrink)

The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is ${\Sigma _1^1 }$ -complete. This result and proof have a number of nice corollaries: the Scott rank of ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly $\Delta (...) _\alpha ^0 $ orbit (from the proof). (shrink)

Reviewed Works:Andrea Sorbi, Complexity, Logic, and Recursion Theory.Klaus Ambos-Spies, Elvira Mayordomo, Resource-Bounded Measure and Randomness.Marat Arslanov, Degree Structures in Local Degree Theory.Jose L. Balcazar, Ricard Gavalda, Montserrat Hermo, Compressibility of Infinite Binary Sequences.S. Barry Cooper, Beyond Godel's Theorem: The Failure to Capture Information Content.Robert A. Di Paola, Franco Montagna, Progressions of Theories of Bounded Arithmetic.Rodney G. Downey, On Presentations of Algebraic Structures.Sophie Fischer, Lane Hemaspaandra, Leen Torenvliet, Witness-Isomorphic Reductions and Local Search.William Gasarch, Carl H. Smith, A Survey of (...) Inductive Inference with an Emphasis on Queries.Andre Nies, A Uniformity of Degree Structures.Piergiorgio Odifreddi, Short Course on Logic, Algebra, and Topology.Andrea Sorbi, The Enumeration Degrees of the $\sigma^0_2$ Sets.Peter van Emde Boas, The Convenience of Tilings. (shrink)

This issue investigates the meaning of photographic image for contemporary art. In Malraux' dream, photography offers the ultimate guarantee for a coherent presentation of art. However, as Douglas Crimp has stated, the appearance and enhancement of photography as a form of art among other art forms disrupted the center of the art world. What does this mean for art and philosophy in our time? Various artists and theorists will delve into that question: Christian Boltanski, Benjamin H.D. Buchloh, Jean-François Chevrier, Douglas (...) Crimp, Jos de Mul, Mirjam de Zeeuw, Rineke Dijkstra, Michael Gibbs, Rodney Graham, Gerald van der Kaap, Karen Knorr, Zoe Leonard, Ken Lum, Hermann Pitz, Liza-May Post, John Roberts, Allan Sekula, Andres Serrano, Jan Simons, Beat Streuli, John M. Swinnen, Renée van de Vall, Hilde van Gelder, Hripsimé Visser, Jeff Wall, Ian Wallace and Herta Wolf. (shrink)

The copious literature on the work of artist Robert Smithson has made very little of the many parallels between the inventor of earthworks and the nineteenth-century author of pataphysics, despite the established fact that the artist read and made notes from Alfred Jarry’s Dr. Faustroll (1898) while working on the Spiral Jetty in 1970, which undoubtedly influenced the subsequent Broken Circle &/ Spiral Hill (1971, Emmen). Given the insightful literature reassessing Jarry’s influence on twentieth-century artists including Marcel Duchamp, John Cage (...) and Rodney Graham, a consideration of Smithson’s spiral earthworks in connection with Jarry is long overdue. In contrast to prevailing art research practices today, Smithson’s work is much more aligned with the pataphysical pursuit of ‘imaginary solutions’ that examine ‘the laws governing exceptions’ and describe ‘a universe which can be – and perhaps should be – envisaged in place of the traditional one’. Art historian Jack Burnham’s interprets Smithson’s earthworks as a ‘time-bound web of man-nature interactions … didactic exercises … [that] show a desperate need for environmental sensibility’. In this respect, the work of both Jarry and Smithson can provide a useful corrective to an overly rationalistic approach to art research, offering the field – and contemporary art in general – potentially valuable tools for forms of practice that challenge rather than adopt conventional academic models and epistemological constructs. (shrink)

The article focuses on the work of Ian Wallace, Jeff Wall and Rodney Graham, in particular, a notion of the studio that provides both an anchor and departure for the work of all three. This genealogy turns primarily on Wallace’s photo-conceptual work from the 1970s, which establishes the space of the studio as an allegory of painting or the modernist tradition, and as the topological equivalent of the museum and street. Using Wallace’s model of post-studio practice as an (...) analytic, the article unpacks the tensions of Wall’s notion of cinematography, highlighting his mounting hesitations with photography understood on the model of the studio system, as an inside/outside relationship and as the mimesis of painting. Finally, the article puts the notions of studio as genealogy and dispositif to work in order to understand the logic of Graham’s emphasis on the durational art of film. (shrink)

In this book the metaphysical system of Graham Harman is presented in lucid form, aided by helpful diagrams. In Chapter 1, Harman gives his most forceful critique to date of philosophies that reject objects as a primary reality. All such rejections are tainted by either an undermining or overmining approach to objects. In Chapters 2 and 3, he reviews his concepts of sensual and real objects. In the process, he attacks the prestige normally granted to philosophies of human access, (...) which Harman links for the first time to the already discredited Menos Paradox. In Chapters 4 through 7, Harman brings the reader up to speed on his interpretation of Heidegger, which culminates in a fourfold structure of objects linked by indirect causation. In Chapter 8, he speculates on the implications of this theory for the debate over panpsychism, which Harman both embraces and rejects. In Chapters 9 and 10, he introduces the term ontography as the study of the different possible permutations of objects and qualities, which he simplifies with easily remembered terminology drawn from standard playing cards. (shrink)

More Speculative Realism Graham Harman. GRAHAM HARMAN BELLS AND WHISTLES MURE SPEBLILATIVE REALISM Bell and Whistles More Speculative Realism Graham Harman Winchester, UK. Front Cover.

Assisted dying is a divisive and controversial topic and it is therefore desirable that a broad range of interests inform any proposed policy changes. The purpose of this study is to collect and synthesize the views of an important stakeholder group—namely people with disabilities —as expressed by disability rights organisations in Great Britain. Parliamentary consultations were reviewed, together with an examination of the contemporary positions of a wide range of DROs. Our analysis revealed that the vast majority do not have (...) a clear public stance; those that do exhibit a significant diversity of opinion. DROs opposing legislation on assisted dying have argued that it would be premature, misguided, inequitable and culturally undesirable. Some specify conditions that would have to be satisfied before they could support legalisation, such as radical improvements in health and social care services and the elimination of discrimination against PwD. DROs supporting assisted dying maintain that a change in the law would promote autonomy, end intense suffering, can be delivered safely and is supported by the DRO’s membership. The discussion considers the reasons why several DROs adopt a neutral stance and the argument is made that, whatever their overarching stance on the issue, DROs need to be involved in the policy debate so that the crucial perspectives of PwD are heard and addressed. This is an important message for countries around the world that permit, or are considering legalising, assisted dying. (shrink)

Altered state theories of hypnosis posit that a qualitatively distinct state of mental processing, which emerges in those with high hypnotic susceptibility following a hypnotic induction, enables the generation of anomalous experiences in response to specific hypnotic suggestions. If so then such a state should be observable as a discrete pattern of changes to functional connectivity (shared information) between brain regions following a hypnotic induction in high but not low hypnotically susceptible participants. Twenty-eight channel EEG was recorded from 12 high (...) susceptible (highs) and 11 low susceptible (lows) participants with their eyes closed prior to and following a standard hypnotic induction. The EEG was used to provide a measure of functional connectivity using both coherence (COH) and the imaginary component of coherence (iCOH), which is insensitive to the effects of volume conduction. COH and iCOH were calculated between all electrode pairs for the frequency bands: delta (0.1–3.9Hz), theta (4–7.9Hz) alpha (8–12.9Hz), beta1 (13–19.9Hz), beta2 (20–29.9Hz) and gamma (30–45Hz). The results showed that there was an increase in theta iCOH from the pre-hypnosis to hypnosis condition in highs but not lows with a large proportion of significant links being focused on a central-parietal hub. There was also a decrease in beta1 iCOH from the pre-hypnosis to hypnosis condition with a focus on a fronto-central and an occipital hub that was greater in high compared to low susceptibles. There were no significant differences for COH or for spectral band amplitude in any frequency band. The results are interpreted as indicating that the hypnotic induction elicited a qualitative change in the organization of specific control systems within the brain for high as compared to low susceptible participants. This change in the functional organization of neural networks is a plausible indicator of the much theorized “hypnotic-state”. (shrink)

M. H. A. Newman (1928) criticized Russell's structuralist philosophy of science. Demopoulos and Friedman have discussed Newman's critique, showing its relevance to the structuralist positions held by Schlick and Carnap, and to Putnam's argument against "metaphysical realism". I discuss Richard Braithwaite's (1940) appeal to Newman in a critique of Arthur Eddington. Braithwaite believed Newman had shown that "structure depends upon content". Eddington, in his reply, misunderstood the generality of Newman's argument.

The manuscript notes described and trascribed below are unique: they show Bacon in the very act of originating, selecting and developing materials for the natural-philosophical projects of the crucial last years of his life. Many of the notes are drafts of material later incorporated in published texts—notably the Sylva Sylvarum . Examination of the drafts indicates that the Sylva is not a hotch-potch of plagiarized scraps. Bacon took great pains, acknowledged borrowings and drew heavily on his own extensive experimental and (...) observational work. The drafts also show that much of the material was used to display the explanatory power of his ambitious speculative philosophy. Preoccupation with the speculative philosophy is also evidenced in the notes which have no counterpart in the published works. Among these notes is a passage on the size of the universe, the motion of the fixed stars and the hypothesis of the earth's diurnal rotation. In that passage Bacon struggled with threats to his unswervingly geostatic conception of the universe. (shrink)

The ArgumentDespite the enormous historical attention psychoanalysis has attracted, its popularization in Britain (as opposed to the United States) in the wake of the Great War has been largely overlooked. The present paper explores the sources and fate of the sudden “craze” for psychoanalysis after 1918, examining the content of the books through which the doctrine became widely known, along with the roles played by religious interests and the popular press. The percolation of Freudian and related language into everyday English (...) was effectively complete by the 1930s. Crucially, it is argued that in Britain the character of psychoanalytic theory itself demonstrably converged with the psychological needs of the British population in the postwar period. The situation in Britain was clearly different in many respects from that in the United States. This episode bears on numerous questions about scientific popularization, the distinctiveness of British psychoanalysis, and though it is treated here only peripherally the epistemological status or nature of psychoanalysis. More generally the present paper may be read as an exercise in reflexive disciplinary historiography, in which the levels of discipline (“Psychology”) and subject matter (“psychology”) are viewed as interpenetrating and mutually constitutive. (shrink)